/*
练习15-4 最长公共子序列
分数 30
作者 陈越
单位 浙江大学

给定序列 X={x1​,x2​,⋯,xn​}，其子序列是从该序列中删去若干元素后得到的序列。一个包含 n 个元素的序列有 2n 个子序列。给定两个序列 X={x1​,x2​,⋯,xn​} 和 Y={y1​,y2​,⋯,ym​}，请设计算法找出 X 和 Y 的一个最长公共子序列。
函数接口定义：

int LCS(char x[], int n, char y[], int m);

其中 x 和 y 为给定的字符串，n 是 x 的长度，m 是 y 的长度。注意字符串数组的下标从 0 开始。函数 LCS 需要在一行中输出一组最长公共子序列，并返回最长公共子序列的长度。最长公共子序列可能是不唯一的，输出任何一组均可。

输入样例：

catcga
gtaccgtca

输出样例：

tcga
4
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define kMaxLen 1000

int LCS(char x[], int n, char y[], int m);

int main(void)
{
    char x[kMaxLen+1], y[kMaxLen+1];
    
    scanf("%s", x);
    scanf("%s", y);
    printf("%d\n", LCS(x, strlen(x), y, strlen(y)));
    
    return 0;
}
/* 你的代码将被嵌在这里 */

int LCS(char x[], int n, char y[], int m) {
    // 定义动态规划表 dp，dp[i][j] 表示 x 的前 i 个字符和 y 的前 j 个字符的最长公共子序列长度
    int dp[n + 1][m + 1];
    int i, j;

    // 初始化 dp 表的第一列，表示 x 的前 i 个字符和空字符串的最长公共子序列长度为 0
    for (i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }

    // 初始化 dp 表的第一行，表示 y 的前 j 个字符和空字符串的最长公共子序列长度为 0
    for (j = 0; j <= m; j++) {
        dp[0][j] = 0;
    }

    // 填充 dp 表
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (x[i - 1] == y[j - 1]) {
                // 如果 x[i-1] == y[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    // 构造最长公共子序列
    char lcs[dp[n][m] + 1];
    i = n;
    j = m;
    int k = dp[n][m];
    while (i > 0 && j > 0) {
        if (x[i - 1] == y[j - 1]) {
            // 如果 x[i-1] == y[j-1]，则该字符属于最长公共子序列
            lcs[k - 1] = x[i - 1];
            i--;
            j--;
            k--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            // 否则，选择 dp[i-1][j] 和 dp[i][j-1] 中较大的一个
            i--;
        } else {
            j--;
        }
    }
    lcs[dp[n][m]] = '\0'; // 添加字符串结束符

    // 输出最长公共子序列
    printf("%s\n", lcs);

    // 返回最长公共子序列的长度
    return dp[n][m];
}